import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Created by zhourh on 2018/9/14.
 *
 * 你将得到一个字符串数组 A。

 如果经过任意次数的移动，S == T，那么两个字符串 S 和 T 是特殊等价的。



 一次移动包括选择两个索引 i 和 j，且 i％2 == j％2，并且交换 S[j] 和 S [i]。

 现在规定，A 中的特殊等价字符串组是 A 的非空子集 S，这样不在 S 中的任何字符串与 S 中的任何字符串都不是特殊等价的。



 返回 A 中特殊等价字符串组的数量。
 
 */
public class GroupsSpecialEquivalentStrings {

    public static void main(String[] args) {
        System.out.println(new GroupsSpecialEquivalentStrings().numSpecialEquivGroups(new String[]{"a","b","c","a","c","c"}));
        System.out.println(new GroupsSpecialEquivalentStrings().numSpecialEquivGroups(new String[]{"aa","bb","ab","ba"}));
        System.out.println(new GroupsSpecialEquivalentStrings().numSpecialEquivGroups(new String[]{"abc","acb","bac","bca","cab","cba"}));
        System.out.println(new GroupsSpecialEquivalentStrings().numSpecialEquivGroups(new String[]{"abcd","cdab","adcb","cbad"}));
    }

    public int numSpecialEquivGroups2(String[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }

        Set<String> set = new HashSet<>();
        for (String s : A) {
            int len = s.length();
            char[] even = new char[len - len / 2];
            char[] odd = new char[len / 2];
        }

        return 0;
    }

    public int numSpecialEquivGroups(String[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }

        List<List<String>> groups = new ArrayList<>();
        for (String s : A) {
            boolean added = false;
            if (!groups.isEmpty()) {
                for (List<String> group : groups) {
                    if (isSpecialEqual(group.get(0), s)) {
                        group.add(s);
                        added = true;
                        break;
                    }
                }
            }
            if (!added) {
                List<String> group = new ArrayList<>();
                group.add(s);
                groups.add(group);
            }

        }

        return groups.size();
    }

    private boolean isSpecialEqual(String s, String t) {
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();

        char[] s1Chars = new char[sChars.length % 2 == 0 ? sChars.length / 2 : tChars.length / 2 + 1];
        char[] s2Chars = new char[sChars.length / 2];

        char[] t1Chars = new char[tChars.length % 2 == 0 ? tChars.length / 2 : tChars.length / 2 + 1];
        char[] t2Chars = new char[tChars.length / 2];

        for (int i = 0; i < sChars.length; i++ ) {
            if ((i & 0x1) == 0) {
                s1Chars[i >> 1] = sChars[i];
            } else {
                s2Chars[i >> 1] = sChars[i];
            }
        }

        for (int i = 0; i < tChars.length; i++ ) {
            if ((i & 0x1) == 0) {
                t1Chars[i >> 1] = tChars[i];
            } else {
                t2Chars[i >> 1] = tChars[i];
            }
        }

        return isAnagram(new String(s1Chars), new String(t1Chars)) && isAnagram(new String(s2Chars), new String(t2Chars));

    }

    private boolean isAnagram(String s, String t) {
        if (s == null || t == null || s.length() != t.length()) {
            return false;
        }


        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();

        int[] sCounts = new int[26];
        int[] tCounts = new int[26];

        for (int i = 0; i < sChars.length; i++) {
            sCounts[sChars[i] - 97]++;
            tCounts[tChars[i] - 97]++;
        }

        for (int i = 0; i < 26; i++) {
            if (sCounts[i] != tCounts[i]) {
                return false;
            }
        }

        return true;
    }
}
